/**
 * 
 */
package grafi;

import java.util.*;

/**
 * @author sflesca
 *
 */
public class SchedulerLagana {

	Grafo g;
	int[] activityTimes;
	
	/**
	 * 
	 */
	public SchedulerLagana(Grafo g, int[] activityTimes) {
		this.g=g;
		this.activityTimes = activityTimes;
	}
	
	int[] schedule(){
		int[] startTimes = new int[g.getN()];

		Arrays.fill(startTimes, 0);
		int[] gradi = calcolaGradiEntrata();
		boolean[] eseguiti = new boolean[g.getN()];
		Arrays.fill(eseguiti, false);
		Queue<Integer> darimuovere = new LinkedList<Integer>();
		for(int i= 0; i<gradi.length; i++)
			if(gradi[i]==0)
				darimuovere.offer(i);
		while(!darimuovere.isEmpty()){
			int a = darimuovere.poll();
			eseguiti[a]=true;
			Iterator<Arco> it=g.adiacenti(a);
			while (it.hasNext()){
				int ad=it.next().fin;
				int st=startTimes[a]+activityTimes[a];
				if (startTimes[ad]<st){
					startTimes[ad]=st;
				}
				gradi[ad]--;
			}
			for(int i= 0; i<gradi.length; i++)
				if(gradi[i]==0&&!eseguiti[i])
					darimuovere.offer(i);
		}
		
		for (int i=eseguiti.length; i<eseguiti.length; i++){
			if (!eseguiti[i]){
				return null;
			}
		}
		
		return startTimes;
	}
	
	private int[] calcolaGradiEntrata() {
		int gradi[]=new int[g.n];
		for (int i=0; i<g.n; i++)
			for (int j=0; j<g.n; j++){
				if (g.arco(i, j)){
					gradi[j]++;
				}
			}
		return gradi;
	}

	public static void main(String[] args){
		Grafo g=new GrafoMA<Arco>(4);
		g.aggiungiArco(new Arco(0,1));
		g.aggiungiArco(new Arco(3,1));
		g.aggiungiArco(new Arco(1,2));
		g.aggiungiArco(new Arco(0,2));
		int t[]={8,2,3,1};
		SchedulerLagana s=new SchedulerLagana(g,t);
		int sc[]=s.schedule();
		for (int i=0; i<sc.length; i++){
			System.out.println(i+": "+sc[i]);
		}
		
		System.out.println("----");
		
		g=new GrafoMA<Arco>(4);
		g.aggiungiArco(new Arco(0,1));
		g.aggiungiArco(new Arco(3,1));
		g.aggiungiArco(new Arco(1,2));
		g.aggiungiArco(new Arco(2,0));		
		s=new SchedulerLagana(g,t);
		sc=s.schedule();
		for (int i=0; i<sc.length; i++){
			System.out.println(i+": "+sc[i]);
		}
		
	}

}
